#include "consultant.h"

Consultant::Consultant()
{
	solution_cost = 0;
	master = 1;
}

Consultant::~Consultant()
{

}

void Consultant::getInput()
{
	assert((cin >> node_count) && "assert Consultant::get()");
	assert((cin >> edge_count) && "assert Consultant::get()");

	int x, y, cost;
	
	edges.reserve(edge_count);

	for(int i = 0; i < edge_count; i++)
	{
		assert((cin >> x) && "assert Consultant::get()");
		assert((cin >> y) && "assert Consultant::get()");
		assert((cin >> cost) && "assert Consultant::get()");

		edges.push_back(Edge(--x, --y, cost));
	}
}

void Consultant::solveA()
{
	/* si no hay aristas salir, nada que hacer */
	if(edges.size() == 0)
		return;

	/* ordenar las aristas por costo */
	sort(edges.begin(), edges.end(), edgeCompare);

	/* Tomar las aristas más baratas y crear disjoint set */
	DisjointSet ds(node_count);

	for(vector< Edge >::const_iterator it = edges.begin(); it != edges.end(); it++)
	{
		if(ds.join(ds.find(it->x), ds.find(it->y)))
		{
			solution.push_back(*it);
			solution_cost += it->cost;
		}
	}
}

void Consultant::solveB()
{
	if(edges.size() == 0)
		return;

	Node *nodes = new Node[node_count]; // O(vertices)

	for(int i = 0; i < node_count; i++) // O(vertices)
	{
		nodes[i].degree = 0;
	}

	/* crear lista de adyacencias */
	for(list< Edge >::const_iterator it = solution.begin(); it != solution.end(); it++) // O(aristas)
	{
		nodes[it->x].adjacency.push_back(it->y);
		nodes[it->y].adjacency.push_back(it->x);
		nodes[it->x].degree++;
		nodes[it->y].degree++;
	}

	queue< int > leafs;

	for(int i = 0; i < node_count; i++) // O(aristas)
	{
		if(nodes[i].degree == 1)
			leafs.push(i);
	}

	int last = 0;

	while(leafs.size() > 0) // O(vertices)
	{
		/* tomo una hoja */
		last = leafs.front();

		/* disminuyo grado */
		nodes[last].degree--;

		/* disminuyo grado de sus adyacentes */

		for(list< int >::const_iterator it = nodes[last].adjacency.begin(); it != nodes[last].adjacency.end(); it++) // O(adjacentes) (ojo es distinto de O(aristas) u O(nodos))
		{
			nodes[*it].degree--;

			/* si se transforma en hoja la agrego a leafs */
			if(nodes[*it].degree == 1)
				leafs.push(*it);
		}

		/* quito la hoja */
		leafs.pop();	
	}

	/* el último nodo que queda es el master */
	master = last+1;

	delete[] nodes;
}

bool Consultant::edgeCompare(Edge e1, Edge e2)
{
	/* devuelve verdadero si e1 es de menor costo que e2 */
	return (e1.cost < e2.cost);
}

ostream& operator<<(ostream &os, const Consultant &c)
{
	os << c.solution_cost << " ";
	os << c.master << " ";

	for(list< Edge >::const_iterator it = c.solution.begin(); it != c.solution.end(); it++)
		os << it->x+1 << " " << it->y+1 << " ";

	os << endl;

	return os;
}